// ml:run = $bin < input
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <map>

using ll = long long;
ll const mo = 1000000007;
ll const maxn = 500;
ll const maxp = 2007;
ll a[maxn][maxn];
ll c[maxn][maxn];
ll pow2[maxn];
ll n, max;

bool not_prime[maxp];
std::vector<ll> prime;

void init_prime()
{
    for (ll i = 2; i < maxp; i++) {
        if (not_prime[i]) continue;
        prime.push_back(i);
        for (ll j = 2 * i; j < maxp; j += i)
            not_prime[j] = true;
    }
}

void init()
{
    memset(a, 0, sizeof(a));
}

ll gauss()
{
    ll i = 0, j = 0;
    for (; i <= max && j < n; ) {
        ll k = i;
        for (; k <= max; k++) if (a[k][j]) break;
        if (k != max + 1) {
            for (ll l = 0; l <= n; l++)
                std::swap(a[i][l], a[k][l]);
            for (ll k = i + 1; k <= max; k++) {
                if (a[k][j])
                    for (ll l = j; l <= n; l++) a[k][l] ^= a[i][l];
            }
            i++;
        }
        j++;
    }
    return n - i;
}

ll quick2(ll x)
{
    if (!x) return 1;
    ll ret = quick2(x / 2);
    ret = (ret * ret) % mo;
    if (x & 1) ret = (ret * 2) % mo;
    return ret;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    init_prime();
    ll T; std::cin >> T;
    for (ll ti = 1; ti <= T; ti++) {
        std::cout << "Case #" << ti << ":\n";
        std::cin >> n;
        init();
        max = 0;
        for (ll i = 0; i < n; i++) {
            ll x;
            std::cin >> x;
            auto tmp = x;
            for (ll j = 0; j < (ll)prime.size() && prime[j] <= tmp; j++) {
                ll p = prime[j];
                for (; !(tmp % p); ) {
                    a[j][i] ^= 1;
                    tmp /= p;
                    max = std::max(max, j);
                }
            }
        }

        std::cout << quick2(gauss()) - 1 << "\n";
    }
}

